package simple;

/**
 * @author 杜伟毅
 * @version 1.0
 * @since 2025/10/06
 * 14. 最长公共前缀
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * <p>
 * 如果不存在公共前缀，返回空字符串 ""。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：strs = ["flower","flow","flight"]
 * 输出："fl"
 * 示例 2：
 * <p>
 * 输入：strs = ["dog","racecar","car"]
 * 输出：""
 * 解释：输入不存在公共前缀。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= strs.length <= 200
 * 0 <= strs[i].length <= 200
 * strs[i] 如果非空，则仅由小写英文字母组成
 * <p>
 * <p>
 */
public class LongestCommonPrefixFinder {
//    public String longestCommonPrefix(String[] strs) {
//        // 处理空数组
//        if (strs == null || strs.length == 0 || strs[0].isEmpty()) return "";
//        //处理只有一个参数的情况
//        if (strs.length < 2) {
//            return String.valueOf(strs[0].charAt(0));
//        }
//
//        StringBuilder sb = new StringBuilder();
//
//        for (int i = 0; i < strs.length; i++) {
//            //第i个参数的第i个字母为模板
//            char c = strs[i].charAt(i);
//
//            if (i != strs.length - 1) {
//                //直接拿第i+1个参数的第i个字母对比第i个参数的第i个字母，不相等直接退出循环
//                if (c != strs[i + 1].charAt(i)) break;
//            }
//
//            //拿到后面的参数,在依次对比
//            for (int j = i + 1; j <= strs.length - 1; j++) {
//                char c1 = strs[j].charAt(i);
//                if (c != c1) break;
//                if (j == strs.length - 1) {
//                    //如果最后一个也相同，那么就代表相同位置的都相同
//                    if (strs[strs.length - 1].charAt(i) == c) {
//                        sb.append(c);
//                    }
//                }
//            }
//        }
//        if (sb.toString().isEmpty()) {
//            return "";
//        }
//        return sb.toString();
//    }

//    public String longestCommonPrefix(String[] strs) {
//        // 处理空数组
//        if (strs == null || strs.length == 0) return "";
//        //处理只有一个参数的情况
//        if (strs.length == 1) return strs[0];
//
//        for (int i = 0;  i < strs[0].length(); i++) {
//            char currentChar = strs[0].charAt(i);
//
//            //检查其它字符串相同位置的字符
//            for (int j = 1; j < strs.length; j++) {
//                //遇到长度不足或字符串不匹配时立即返回
//                if (i>=strs[j].length()|| strs[j].charAt(i)!=currentChar){
//                    return strs[0].substring(0,i);
//                }
//            }
//        }
//        return strs[0];
//    }

    public String longestCommonPrefix(String[] strs) {
        // 1. 没人来？散会！(空数组)
        if (strs == null || strs.length == 0) return "";
        // 2. 就一个人？他说啥就是啥！(整个字符串就是前缀)
        if (strs.length == 1) return strs[0];

        // 3. 选第一个当"班长" (strs[0])
        // 4. 盯着"班长"的名字，从第一个字母开始看 (i 从 0 开始)
        for (int i = 0; i < strs[0].length(); i++) {
            char currentChar = strs[0].charAt(i); // 班长当前这个字母是啥

            // 5. 开始"点名"！检查其他所有人 (j 从 1 开始)
            for (int j = 1; j < strs.length; j++) {
                // 5.1 点名：张三！
                //     张三：到！(长度够，有第i个位置) 且 说的字母跟班长一样 -> 过关，检查下一个
                //     张三：没来！(长度不够，i位置不存在) 或者 说的字母跟班长不一样！
                if (i >= strs[j].length() || strs[j].charAt(i) != currentChar) {
                    // 5.2 发现有人不符合！立刻结束会议！
                    //      公共前缀就是班长名字的前 i 个字母 (从0到i-1)
                    return strs[0].substring(0, i);
                }
            }
            // 6. 这一轮点名所有人都符合！继续看班长的下一个字母 (i++)
        }
        // 7. 班长的名字从头到尾都符合要求！整个班长名字就是公共前缀
        return strs[0];
    }


    public static void main(String[] args) {
//        String[] strs = {"flower", "flow", "flight"};
//        String[] strs ={"dog","racecar","car"};
//        String[] strs = {"a"};
        String[] strs = {"ab", "a"};
        LongestCommonPrefixFinder finder = new LongestCommonPrefixFinder();
        System.out.println(finder.longestCommonPrefix(strs));
    }
}
